package org.cy.algorithm.chapter_06;

import org.cy.algorithm.util.AlgorithmUtil;

public class MiniHeap_6_5_3 {

    private final int[] arr;
    private int size;

    public MiniHeap_6_5_3(int n) {
        this.size = 0;
        this.arr = new int[n];
    }

    public int heapMinimum() {
        if (size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        return arr[0];
    }

    public int heapExtractMin() {
        if (size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        int min = arr[0];
        arr[0] = arr[--size];
        heapify(0);
        return min;
    }

    public void heapify(int i) {
        int left = 2 * i + 1;
        int right = 2 * (i + 1);
        int minimum = i;
        if (left < size && arr[left] < arr[minimum]) {
            minimum = left;
        }
        if (right < size && arr[right] < arr[minimum]) {
            minimum = right;
        }
        if (minimum != i) {
            AlgorithmUtil.swap(arr, minimum, i);
            heapify(minimum);
        }
    }

    public void heapDecreaseKey(int[] arr, int i, int k) {
        if (k > arr[i]) {
            throw new IllegalArgumentException(String.format("{} should not be greater than {}", k, arr[i]));
        }

        // 使用插值排序的思想，只用一次赋值，按成交换
//        arr[i] = k;
        while (i > 0 && arr[parent(i)] > k) {
//            AlgorithmUtil.swap(arr, parent(i), i);
            arr[i] = arr[parent(i)];
            i = parent(i);
        }
        arr[i] = k; // 使用交换的话，这一行需要删掉
    }

    public int parent(int i) {
        return (i - 1) / 2;
    }

    public void minHeapInsert(int k) {
        arr[size] = Integer.MAX_VALUE;
        heapDecreaseKey(arr, size, k);
        size++;
    }

    public void heapDelete(int i) {
        // 可以把最后一个元素，移到i位置，然后heapify
        arr[i] = arr[--size];
        heapify(i);
    }

    public static void main(String[] args) {
        MiniHeap_6_5_3 heap = new MiniHeap_6_5_3(10);
        heap.minHeapInsert(5);
        heap.minHeapInsert(7);
        heap.minHeapInsert(3);
        heap.minHeapInsert(2);
        heap.minHeapInsert(1);

        heap.heapDelete(2);
//        System.out.println(heap.heapMinimum());
        System.out.println(heap.heapExtractMin());
        System.out.println(heap.heapExtractMin());
        System.out.println(heap.heapExtractMin());
        System.out.println(heap.heapExtractMin());
//        System.out.println(heap.heapExtractMin());
    }
}
